﻿using System.Collections.Generic;
using System.Linq;

namespace maximal_clique
{
    /// <summary>
    /// Represents a set of nodes that can be dependent upon each other, 
    /// and will detect circular dependencies between its nodes.
    /// </summary>
    public class Graph
    {
        #region Constructor

        public Graph(string title)
        {
            this.cliques = new List<Clique>();
            this.Nodes = new List<Node>();
            this.Title = title;
        }

        #endregion // Constructor

        #region Properties

        public List<Clique> cliques { get; private set; }

        public bool HasCircularDependency
        {
            get { return this.cliques.Any(); }
        }

        public List<Node> Nodes { get; private set; }

        public string Title { get; private set; }

        #endregion // Properties

        #region Methods

        /// <summary>
        /// Find all maxmiall cliques in the graph
        /// add them to graph::cliques
        /// </summary>
        public void find_all_cliques()
        {
            
            //employ Bron–Kerbosch algorithm;
            var result = new List<Clique>();
            bron_kerbosch(new List<Node>(), new List<Node>( this.Nodes ), new List<Node>(), ref result);
            this.cliques = result;

            //inform nodes that they are in clique:
            foreach (Clique c in this.cliques)
            {
                foreach (Node n in c.Nodes)
                {
                    n.cliques.Add(c);
                }
            }
        }
        
        private void bron_kerbosch(List<Node> R, List<Node> P, List<Node> X, ref List<Clique> result)
        //private void bron_kerbosch(List<Node> R, List<Node> P, List<Node> X)
        {
            if (P.Any())
            {
                //select x in P, for each v in P \ N(x):
                var x = P[0];
                var P_loop = new List<Node>(P);
                foreach (Node v in P_loop)
                {
                    if (x.NodeDependencies.IndexOf(v) != -1)
                        continue;

                    //BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
                    List<Node> r1 = R.Union(new List<Node> { v }).ToList(); ;
                    List<Node> p1 = P.Intersect(v.NodeDependencies).ToList();
                    List<Node> x1 = X.Intersect(v.NodeDependencies).ToList();
                    bron_kerbosch(r1, p1, x1, ref result);

                    //P := P \ {v}
                    //X := X ⋃ {v}
                    P.Remove(v);
                    X.Add(v);
                }
            }
            else if (!X.Any() && R.Count > 2)  //We don't count 2-clique
            {
                
                Clique a = new Clique(R);
                result.Add(a);
            }
        }


        /// <summary>
        /// Inspects the graph's nodes for circular dependencies.
        /// </summary>
        public void CheckForCircularDependencies()
        {
            foreach (Node node in this.Nodes)
            {
                var circularDependencies = node.FindCircularDependencies();
                if (circularDependencies != null)
                    this.ProcessCircularDependencies(circularDependencies);
            }

            this.cliques.Sort();
        }

        void ProcessCircularDependencies(List<Clique> circularDependencies)
        {
            foreach (Clique circularDependency in circularDependencies)
            {
                if (circularDependency.Nodes.Count == 0)
                    continue;

                if (this.cliques.Contains(circularDependency))
                    continue;

                // Arrange the nodes into the order in which they were discovered.
                circularDependency.Nodes.Reverse();

                this.cliques.Add(circularDependency);

                // Inform each node that it is a member of the circular dependency.
                foreach (Node dependency in circularDependency.Nodes)
                    dependency.cliques.Add(circularDependency);
            }
        }

        public List<List<int>> ChuyenSangDanhSachKe()
        {
            List<List<int>> danhsachke = new List<List<int>>();
            for (int i = 0; i < this.Nodes.Count; i++)
            {
                danhsachke.Add(new List<int>());
                foreach (Node n in this.Nodes[i].NodeDependencies)
                {
                    int j = this.Nodes[i].NodeDependencies.IndexOf(n);
                    danhsachke[danhsachke.Count - 1].Add(j);
                }
            }
            return danhsachke;
        }
        public float[,] ChuyenSangMatran( ref int level, bool IsUndirectGraph)
        {
            return graph_operation.ChuyenSangMatran(this.ChuyenSangDanhSachKe(), ref level, IsUndirectGraph);
        }

        #endregion // Methods
    }
}